package sol.leetcode;

/**
 * Patching Array
 */
public class Issue330 {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int i = 0;
        int res = 0;

        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                res++;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 11, 30};
        int n = 50;
        Issue330 sol = new Issue330();
        System.out.println(sol.minPatches(nums, n));
    }
}
